package chapter04;

import util.ArrayUtil;

/**
 * @ClassName QuickSort
 * @Description: 快速排序  以数组最后一个数做三个分区 小于区在最左 等于区在中间 大于区在最右
 * @Author: WangWenpeng
 * @date: 17:56 2021/8/29
 * @Version 1.0
 */
public class QuickSort {

    public static void main(String[] args) {
        //int[] arr = {7, 1, 3, 5, 4, 5, 1, 4, 2, 4, 2, 4};
        int[] arr = {7, 1, 3, 5, 2, 4, 5};
        ArrayUtil.printArray(arr);
        quickSort(arr);
        ArrayUtil.printArray(arr);
    }

    private static void quickSort(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalArea = partition(arr, L, R);
        process(arr, L, equalArea[0] - 1);
        process(arr, equalArea[1] + 1, R);
    }

    /**
     * arr[L...R]范围上，拿arr[R]做划分值
     * 分为最左边小于区，中间等于区 右边大于区
     */
    private static int[] partition(int[] arr, int L, int R) {
        int lessThanRIndex = L - 1;
        int moreThanRIndex = R;
        int index = L;
        while (index < moreThanRIndex) {
            if (arr[index] < arr[R]) {
                //ArrayUtil.swap(arr, index, lessThanRIndex + 1);
                //lessThanRIndex++;
                //index++;
                ArrayUtil.swap(arr, ++lessThanRIndex, index++);
            } else if (arr[index] > arr[R]) {
                ArrayUtil.swap(arr, --moreThanRIndex, index);
            } else {
                index++;
            }
            ArrayUtil.printArray(arr);
        }
        ArrayUtil.swap(arr, moreThanRIndex, R);
        ArrayUtil.printArray(arr);
        return new int[]{lessThanRIndex + 1, moreThanRIndex};
    }
}
